As a control device of a conventional internal combustion engine mounted on a vehicle, patent literature 1 describes, for example, a starting device of the internal combustion engine that can start the internal combustion engine by igniting fuel supplied to a cylinder in an expansion stroke. The starting device of the internal combustion engine predicts an operation state of a crank of when ignition is carried out on the cylinder in the expansion stroke while a starter is not operating, and determines whether or not to operate the starter based on the predicted operation state of the crank. If determined that a piston of a cylinder following the cylinder in the expansion stroke does not exceed a compression top dead center with only an initial explosion, for example, the starting device of the internal combustion engine starts a starter motor after the crank is operated by the initial explosion.